The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Packet forwarding decisions and other packet operations are demanding parts of switch and router design. For example, IP forwarding requires a longest prefix matching computation at wire speeds. The current IP version, IPv4, uses 32-bit destination addresses and a core Internet router can have over 200,000 prefixes. A prefix typically refers to a value which ends in zero or more bits which are “don't care” or wildcard bits (i.e., these wildcard bits are considered to match both a zero and a one). For example, a 32-bit prefix could contain thirty-two bits of zeros and/or ones (i.e., no wildcard bits), or contain less than thirty-two bits with the trailing bits being wildcard bits. These prefixes are typically denoted by a bit string (e.g., 01*) followed by a ‘*’, by a “value/number of relevant bits” (e.g., 01001010/8) to indicate a value of the prefix with the remaining trailing bits after the number of relevant bits being wildcard bits (i.e., do not matter), or by a fully expanded value (e.g., 01000101010101010101010101010101, 45555555 Hex, 69:85:85:85, etc.).
For destination routing, each prefix entry in a routing table typically consists of a prefix and a next hop value. For example, suppose the database consists of two prefix entries: 01-->L1, and 0100/4-->L2. If the router receives a packet with destination address that starts with 0100, the address matches both the first prefix (01*) and the second prefix (0100/4). Because the second prefix is the longest matching prefix in the routing database, the packet should be sent to next hop L2. On the other hand, a packet with destination address that starts with 011 should be sent to next hop L1. The next hop information will typically specify an output port on the router and possibly a data link address.
Various software and hardware implementations are used to identify a longest matching prefix, each typically having a different performance, memory, associative memory requirements, scalability and updating requirements. Needed are new methods and apparatus for identifying a longest matching prefix, which may be particularly useful for certain applications and implementations, and may have one or more advantages over one or more prior implementations.